package offer;

import java.util.LinkedList;
import java.util.List;

@FunctionalInterface
public interface PathInZigZagTree {
    /**
     * 在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
     *
     * 如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
     *
     * 而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
     *
     * 给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
     * @param label
     * @return
     */
    List<Integer> pathInZigZagTree(int label);
}
class PathInZigZagTreeImpl1 implements PathInZigZagTree{
    public static void main(String[] args) {
        List<Integer> ans = new PathInZigZagTreeImpl1().pathInZigZagTree(14);

        for(int num : ans){
            System.out.println(ans);
        }
    }

    /**
     * 时间o(logn),空间o（1）
     * 考虑坐标转换，将之字形的二叉树转换为常规的层序遍历递增的二叉树的坐标。
     * 关键点是这一句，表示了两个二叉树的映射关系
     * label = curLevelNums * 3 - 1 - label;
     *
     * @param label
     * @return
     */
    @Override
    public List<Integer> pathInZigZagTree(int label) {
        int height = getHeight(label);
        int curLevelNums = 1;
        List<Integer> ans = new LinkedList<>();
        for (int i = 0; i < height - 1; i++) {
            curLevelNums *= 2;
        }
        while(height != 0){
            ans.add(label);
            if(height % 2 == 1){
                // 当前是奇数层，下一层是偶数层，坐标转换
                label/=2;
                curLevelNums/=2;
                label = curLevelNums * 3 - 1 - label;
            }else{
                // 当前是偶数层，下一层是奇数层，坐标转换
                // 将label转为层序坐标
                label = curLevelNums * 3 - 1 - label;
                label/=2;
                curLevelNums/=2;
            }
            height--;
        }
        return ans;
    }
    private int getHeight(int label){
        int iter = 0;
        while(label != 0){
            label/=2;
            iter++;
        }
        return iter;
    }
}